package com.leecode.xiehf.page_02;

import com.leecode.Printer;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2->3->4->5->NULL, k = 2
 * 输出: 4->5->1->2->3->NULL
 * 解释:
 * 向右旋转 1 步: 5->1->2->3->4->NULL
 * 向右旋转 2 步: 4->5->1->2->3->NULL
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/rotate-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0061 extends Printer {

    public static void main(String[] args) {
        Solution_0061 solution = new Solution_0061();
        ListNode first =
                new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, new ListNode(7, null)))))));

        ListNode s = solution.rotateRight(first, 8);
        while (s != null) {
            System.out.println(s.val);
            s = s.next;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null) {
            return head;
        }
        ListNode curr = head;
        int len = 0;
        ListNode end = null;
        while (curr != null) {
            len++;
            if (curr.next == null) {
                end = curr;
            }
            curr = curr.next;
        }
        // 取模 得到需要移动的位数
        int step = k % len;
        if (step == 0) {
            return head;
        }
        // 计算从第几个节点开始截断
        int index = len - step;

        // 从第一个开始
        ListNode node = head;

        // 结果指向的指针
        ListNode res = null;
        while (index > 0) {
            index--;
            if (index == 0) {
                end.next = head;
                res = node.next;
                node.next = null;
            }
            node = node.next;
        }
        return res;
    }

}
